//给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充
//。
// 
// 
// 
//
// 示例 1： 
//
// 
//输入：board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X"
//,"X"]]
//输出：[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
//解释：被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都
//会被填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。
// 
//
// 示例 2： 
//
// 
//输入：board = [["X"]]
//输出：[["X"]]
// 
//
// 
//
// 提示： 
//
// 
// m == board.length 
// n == board[i].length 
// 1 <= m, n <= 200 
// board[i][j] 为 'X' 或 'O' 
// 
// 
// 
// Related Topics 深度优先搜索 广度优先搜索 并查集 数组 矩阵 
// 👍 669 👎 0

package com.cute.leetcode.editor.cn;
public class SurroundedRegions {
    public static void main(String[] args) {
        Solution solution = new SurroundedRegions().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 思路是这样的：遍历四条边去找入口
         * 找到入口之后dfs遍历所有可以访问到的地方，并使用alive数组保存其位置
         * 最后再遍历除去四周的所有下标，将不再alive数组中的 O 都赋值为 X 即可
         */
        int row;
        int col;
        boolean[][] alive;
        public void solve(char[][] board) {
            row = board.length;
            col = board[0].length;
            alive = new boolean[row][col];
            for (int i = 0; i < col; i++) {
                if (board[0][i]=='O')
                    dfs(0, i, board);
            }
            for (int i = 0; i < row; i++) {
                if (board[i][0]=='O')
                    dfs(i, 0, board);
            }
            for (int i = 0; i < col; i++) {
                if (board[row-1][i]=='O')
                    dfs(row-1, i, board);
            }
            for (int i = 0; i < row; i++) {
                if (board[i][col-1]=='O')
                    dfs(i, col-1, board);
            }
            for (int i = 1; i < row-1; i++) {
                for (int j = 1; j < col-1; j++) {
                    if (board[i][j]=='O'&&!alive[i][j])
                        board[i][j]='X';
                }
            }
        }
        public void dfs(int i, int j, char[][] board){
            if (inGrid(i, j)&&board[i][j]=='O'&&!alive[i][j]){
                alive[i][j] = true;
                dfs(i, j+1, board);
                dfs(i, j-1, board);
                dfs(i+1, j, board);
                dfs(i-1, j, board);
            }
        }

        public boolean inGrid(int x, int y){
            return x>=0 && x<row && y>=0 && y<col;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}